﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sort
{
    static class HeapSort
    {
        static void Main()
        {
            Console.WriteLine("HeapSort.");
            //int[] arr = { 6, 0, 1, 1, 7, 13, 14, 6, 11, 4 };
            //Random rd = new Random();
            //for (int j = 0; j < 1000; j++)
            //{
            //    for (int i = 0; i < 10; i++)
            //    {
            //        arr[i] = rd.Next(20);
            //    }
            //    Sort(arr);
            //    if (!Utils.CheckOrderArray(arr))
            //    {
            //        Console.WriteLine("error.");
            //    }
            //    //Utils.WriteArr(arr);
            //}
            int[] arr = { 10, 8, 11, 18, 9, 6, 7 };
            Sort(arr);
        }

        static void HeapAdjust(int[] array, int parent, int length)
        {
            int temp = array[parent]; // temp保存当前父节点
            int child = 2 * parent + 1; // 先获得左孩子

            while (child < length)
            {
                // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
                if (child + 1 < length && array[child] < array[child + 1])
                {
                    child++;
                }

                // 如果父结点的值已经大于孩子结点的值，则直接结束
                if (temp >= array[child])
                    break;

                // 把孩子结点的值赋给父结点
                array[parent] = array[child];

                // 选取孩子结点的左孩子结点,继续向下筛选
                parent = child;
                child = 2 * child + 1;
            }

            array[parent] = temp;
        }

        public static void Sort(int[] list)
        {
            // 循环建立初始堆
            for (int i = list.Length / 2; i >= 0; i--) {
                HeapAdjust(list, i, list.Length);
            }
 
            // 进行n-1次循环，完成排序
            for (int i = list.Length - 1; i > 0; i--) {
                // 最后一个元素和第一元素进行交换
                Utils.Swap(list, 0, i);
                // 筛选 R[0] 结点，得到i-1个结点的堆
                HeapAdjust(list, 0, i);
            }
        }
 

        public static void Sort1(int[] arr)
        {
            InitHeap(arr);

            int len = arr.Length;
            for (int i = 1; i < len; i++)
            {
                HeapAdjust1(arr, len - i);
            }
        }

        static void HeapAdjust1(int[] arr, int end)
        {
            Utils.Swap(arr, 0, end);

            int result = HeapNodeAdjust(arr, 0, end - 1, 0);
            while (result != -1)
            {
                result = HeapNodeAdjust(arr, 0, end - 1, result);
            }
        }

        //调整堆（数组arr的beg到end部分）的父节点为idx的节点
        static int HeapNodeAdjust(int[] arr, int beg, int end, int idx)
        {
            if (beg == end)
                return -1;

            if (idx < beg)
                return -1;

            int heapIdx = idx - beg;
            int heapEndIdx = end - beg;

            if (heapIdx * 2 + 1 > heapEndIdx)
                return -1;

            int leftChildIdx = heapIdx * 2 + 1;
            int rightChildIdx = leftChildIdx + 1;
            int leftChildValue = arr[leftChildIdx + beg];
            int parentIdx = (heapIdx-1) / 2;

            int value = arr[heapIdx + beg];
            if (rightChildIdx <= heapEndIdx)
            {
                int bigIdx = leftChildIdx;
                int bigValue = leftChildValue;
                if (arr[rightChildIdx + beg] > leftChildValue)
                {
                    bigIdx = rightChildIdx;
                    bigValue = arr[rightChildIdx + beg];
                }

                if (bigValue > value)
                {
                    Utils.Swap(arr, bigIdx + beg, heapIdx + beg);
                    return bigIdx + beg;
                }
            }
            else
            {
                if (arr[leftChildIdx + beg] > value)
                {
                    Utils.Swap(arr, heapIdx + beg, leftChildIdx + beg);
                    return leftChildIdx + beg;
                }
            }
            return -1;
        }

        static void InitHeap(int[] arr)
        {
            int len = arr.Length;
            for (int i = 0; i < len; i++)
            {
                int heapIdx = i;
                while (HeapNodeAdjust(arr, 0, len - 1, heapIdx) != -1)
                {
                    int parentIdx = (heapIdx - 1) / 2;
                    heapIdx = parentIdx;
                }

                heapIdx = i;
                while (HeapNodeAdjust(arr, 0, len - 1, heapIdx) != -1)
                {
                    int parentIdx = (heapIdx - 1) / 2;
                    heapIdx = parentIdx;
                }
            }
        }
    }
}
